package com.laotang.第_1_章_数组和字符串.力扣_68_文本左右对齐;

import java.util.ArrayList;
import java.util.List;

public class _68_text_justification {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<>();

        int n = words.length;
        int left = 0, right = 0;

        while (true) {
            // 1. 确定当前行可以放哪些单词
            left = right;
            int sumLen = 0;
            while (right < n && sumLen + words[right].length() + (right - left) <= maxWidth) {
                sumLen += words[right].length();
                right++;
            }
            // 至此，可以确定当前行存放的单词是：words[left...right - 1]

            if (right == n) {
                // 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格
                StringBuilder sb = join(words, left, right, " ");
                sb.append(blank(maxWidth - sb.length()));
                ans.add(sb.toString());
                return ans;
            }

            int numWords = right - left;
            int numSpaces = maxWidth - sumLen;
            if (numWords == 1) {
                // 当前行只有一个单词：该单词左对齐，在行末填充剩余空格
                StringBuilder sb = new StringBuilder(words[left]);
                sb.append(blank(numSpaces));
                ans.add(sb.toString());
                continue;
            }

            // 当前行不只一个单词
            // 计算两个单词之间需要多少个空格 （求平均值，因为要均匀分配）
            int avgSpaces = numSpaces / (numWords - 1);
            // 如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
            /*
            "This    is    an   example   ok   my"
            maxWidth = 36
            sumLen = 19，numSpaces = 17
            17 / 5 = 3
             */
            // 计算均匀分配后，还剩多少个额外的空格  17 % 5 = 2
            int extraSpaces = numSpaces % (numWords - 1);
            StringBuilder sb = new StringBuilder();

            sb.append(join(words, left, left + extraSpaces + 1, blank(avgSpaces + 1)));
            sb.append(blank(avgSpaces));
            sb.append(join(words, left + extraSpaces + 1, right, blank(avgSpaces)));
            ans.add(sb.toString());
        }
    }

    // join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串
    // 比如 words = {"This", "is", "an", "example", "of", "text", "justification."}
    // join(words, 2, 5, "   ") --> "an   example   of"
    public StringBuilder join(String[] words, int left, int right, String sep) {
        StringBuilder sb = new StringBuilder(words[left]);
        for (int i = left + 1; i < right; ++i) {
            sb.append(sep);
            sb.append(words[i]);
        }
        return sb;
    }

    // blank 返回长度为 n 的由空格组成的字符串
    public String blank(int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            sb.append(' ');
        }
        return sb.toString();
    }
}
